home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Tools / MPW / gzip 1.2.2 / unlzh.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-06-22  |  8.5 KB  |  386 lines  |  [TEXT/MPS ]
  1. /* unlzh.c -- decompress files in SCO compress -H (LZH) format.
  2.  * The code in this file is directly derived from the public domain 'ar002'
  3.  * written by Haruhiko Okumura.
  4.  */
  5.  
  6. #include <stdio.h>
  7.  
  8. #include "tailor.h"
  9. #include "gzip.h"
  10. #include "lzw.h" /* just for consistency checking */
  11.  
  12. /* decode.c */
  13.  
  14. local unsigned  decode  OF((unsigned count, uch buffer[]));
  15. local void decode_start OF((void));
  16.  
  17. /* huf.c */
  18. local void huf_decode_start OF((void));
  19. local unsigned decode_c     OF((void));
  20. local unsigned decode_p     OF((void));
  21.  
  22. /* io.c */
  23. local void fillbuf      OF((int n));
  24. local unsigned getbits  OF((int n));
  25. local void init_getbits OF((void));
  26.  
  27. #define DICBIT    13    /* 12(-lh4-) or 13(-lh5-) */
  28. #define DICSIZ ((unsigned) 1 << DICBIT)
  29.  
  30. #ifndef CHAR_BIT
  31. #  define CHAR_BIT 8
  32. #endif
  33.  
  34. #ifndef UCHAR_MAX
  35. #  define UCHAR_MAX 255
  36. #endif
  37.  
  38. #define BITBUFSIZ (CHAR_BIT * 2 * sizeof(char))
  39. /* Do not use CHAR_BIT * sizeof(bitbuf), does not work on machines
  40.  * for which short is not on 16 bits (Cray).
  41.  */
  42.  
  43. /* encode.c and decode.c */
  44.  
  45. #define MAXMATCH 256    /* formerly F (not more than UCHAR_MAX + 1) */
  46. #define THRESHOLD  3    /* choose optimal value */
  47.  
  48. /* huf.c */
  49.  
  50. #define NC (UCHAR_MAX + MAXMATCH + 2 - THRESHOLD)
  51.     /* alphabet = {0, 1, 2, ..., NC - 1} */
  52. #define CBIT 9  /* $\lfloor \log_2 NC \rfloor + 1$ */
  53. #define CODE_BIT  16  /* codeword length */
  54.  
  55. #define NP (DICBIT + 1)
  56. #define NT (CODE_BIT + 3)
  57. #define PBIT 4  /* smallest integer such that (1U << PBIT) > NP */
  58. #define TBIT 5  /* smallest integer such that (1U << TBIT) > NT */
  59. #if NT > NP
  60. # define NPT NT
  61. #else
  62. # define NPT NP
  63. #endif
  64.  
  65. /* local ush left[2 * NC - 1]; */
  66. /* local ush right[2 * NC - 1]; */
  67. #define left  prev
  68. #define right head
  69. #if NC > 1<<(BITS-2)
  70.     error cannot overlay left+right and prev
  71. #endif
  72.  
  73. /* local uch c_len[NC]; */
  74. #define c_len outbuf
  75. #if NC > OUTBUFSIZ
  76.     error cannot overlay c_len and outbuf
  77. #endif
  78.  
  79. local uch pt_len[NPT];
  80. local unsigned blocksize;
  81. local ush pt_table[256];
  82.  
  83. /* local ush c_table[4096]; */
  84. #define c_table d_buf
  85. #if DIST_BUFSIZE < 4096
  86.     error cannot overlay c_table and d_buf
  87. #endif
  88.  
  89. local ush       bitbuf;
  90. local unsigned  subbitbuf;
  91. local int       bitcount;
  92.  
  93. local void fillbuf(n)  /* Shift bitbuf n bits left, read n bits */
  94.     int n;
  95. {
  96.     bitbuf <<= n;
  97.     while (n > bitcount) {
  98.     bitbuf |= subbitbuf << (n -= bitcount);
  99.     subbitbuf = (unsigned)try_byte();
  100.     if ((int)subbitbuf == EOF) subbitbuf = 0;
  101.     bitcount = CHAR_BIT;
  102.     }
  103.     bitbuf |= subbitbuf >> (bitcount -= n);
  104. }
  105.  
  106. local unsigned getbits(n)
  107.     int n;
  108. {
  109.     unsigned x;
  110.  
  111.     x = bitbuf >> (BITBUFSIZ - n);  fillbuf(n);
  112.     return x;
  113. }
  114.  
  115. local void init_getbits()
  116. {
  117.     bitbuf = 0;  subbitbuf = 0;  bitcount = 0;
  118.     fillbuf(BITBUFSIZ);
  119. }
  120.  
  121. /***********************************************************
  122.     maketbl.c -- make table for decoding
  123. ***********************************************************/
  124.  
  125. local void make_table(nchar, bitlen, tablebits, table)
  126.     int nchar;
  127.     uch bitlen[];
  128.     int tablebits;
  129.     ush table[];
  130. {
  131.     ush count[17], weight[17], start[18], *p;
  132.     unsigned i, k, len, ch, jutbits, avail, nextcode, mask;
  133.  
  134.     for (i = 1; i <= 16; i++) count[i] = 0;
  135.     for (i = 0; i < nchar; i++) count[bitlen[i]]++;
  136.  
  137.     start[1] = 0;
  138.     for (i = 1; i <= 16; i++)
  139.     start[i + 1] = start[i] + (count[i] << (16 - i));
  140.     if (start[17] != (ush)((unsigned) 1 << 16))
  141.     error("Bad table\n");
  142.  
  143.     jutbits = 16 - tablebits;
  144.     for (i = 1; i <= tablebits; i++) {
  145.     start[i] >>= jutbits;
  146.     weight[i] = (unsigned) 1 << (tablebits - i);
  147.     }
  148.     while (i <= 16) {
  149.     weight[i] = (unsigned) 1 << (16 - i);
  150.     i++;
  151.     }
  152.  
  153.     i = start[tablebits + 1] >> jutbits;
  154.     if (i != (ush)((unsigned) 1 << 16)) {
  155.     k = 1 << tablebits;
  156.     while (i != k) table[i++] = 0;
  157.     }
  158.  
  159.     avail = nchar;
  160.     mask = (unsigned) 1 << (15 - tablebits);
  161.     for (ch = 0; ch < nchar; ch++) {
  162.     if ((len = bitlen[ch]) == 0) continue;
  163.     nextcode = start[len] + weight[len];
  164.     if (len <= tablebits) {
  165.         for (i = start[len]; i < nextcode; i++) table[i] = ch;
  166.     } else {
  167.         k = start[len];
  168.         p = &table[k >> jutbits];
  169.         i = len - tablebits;
  170.         while (i != 0) {
  171.         if (*p == 0) {
  172.             right[avail] = left[avail] = 0;
  173.             *p = avail++;
  174.         }
  175.         if (k & mask) p = &right[*p];
  176.         else          p = &left[*p];
  177.         k <<= 1;  i--;
  178.         }
  179.         *p = ch;
  180.     }
  181.     start[len] = nextcode;
  182.     }
  183. }
  184.  
  185. /***********************************************************
  186.         huf.c -- static Huffman
  187. ***********************************************************/
  188.  
  189. local void read_pt_len(nn, nbit, i_special)
  190.     int nn;
  191.     int nbit;
  192.     int i_special;
  193. {
  194.     int i, c, n;
  195.     unsigned mask;
  196.  
  197.     n = getbits(nbit);
  198.     if (n == 0) {
  199.     c = getbits(nbit);
  200.     for (i = 0; i < nn; i++) pt_len[i] = 0;
  201.     for (i = 0; i < 256; i++) pt_table[i] = c;
  202.     } else {
  203.     i = 0;
  204.     while (i < n) {
  205.         c = bitbuf >> (BITBUFSIZ - 3);
  206.         if (c == 7) {
  207.         mask = (unsigned) 1 << (BITBUFSIZ - 1 - 3);
  208.         while (mask & bitbuf) {  mask >>= 1;  c++;  }
  209.         }
  210.         fillbuf((c < 7) ? 3 : c - 3);
  211.         pt_len[i++] = c;
  212.         if (i == i_special) {
  213.         c = getbits(2);
  214.         while (--c >= 0) pt_len[i++] = 0;
  215.         }
  216.     }
  217.     while (i < nn) pt_len[i++] = 0;
  218.     make_table(nn, pt_len, 8, pt_table);
  219.     }
  220. }
  221.  
  222. local void read_c_len()
  223. {
  224.     int i, c, n;
  225.     unsigned mask;
  226.  
  227.     n = getbits(CBIT);
  228.     if (n == 0) {
  229.     c = getbits(CBIT);
  230.     for (i = 0; i < NC; i++) c_len[i] = 0;
  231.     for (i = 0; i < 4096; i++) c_table[i] = c;
  232.     } else {
  233.     i = 0;
  234.     while (i < n) {
  235.         c = pt_table[bitbuf >> (BITBUFSIZ - 8)];
  236.         if (c >= NT) {
  237.         mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
  238.         do {
  239.             if (bitbuf & mask) c = right[c];
  240.             else               c = left [c];
  241.             mask >>= 1;
  242.         } while (c >= NT);
  243.         }
  244.         fillbuf((int) pt_len[c]);
  245.         if (c <= 2) {
  246.         if      (c == 0) c = 1;
  247.         else if (c == 1) c = getbits(4) + 3;
  248.         else             c = getbits(CBIT) + 20;
  249.         while (--c >= 0) c_len[i++] = 0;
  250.         } else c_len[i++] = c - 2;
  251.     }
  252.     while (i < NC) c_len[i++] = 0;
  253.     make_table(NC, c_len, 12, c_table);
  254.     }
  255. }
  256.  
  257. local unsigned decode_c()
  258. {
  259.     unsigned j, mask;
  260.  
  261.     if (blocksize == 0) {
  262.     blocksize = getbits(16);
  263.     if (blocksize == 0) {
  264.         return NC; /* end of file */
  265.     }
  266.     read_pt_len(NT, TBIT, 3);
  267.     read_c_len();
  268.     read_pt_len(NP, PBIT, -1);
  269.     }
  270.     blocksize--;
  271.     j = c_table[bitbuf >> (BITBUFSIZ - 12)];
  272.     if (j >= NC) {
  273.     mask = (unsigned) 1 << (BITBUFSIZ - 1 - 12);
  274.     do {
  275.         if (bitbuf & mask) j = right[j];
  276.         else               j = left [j];
  277.         mask >>= 1;
  278.     } while (j >= NC);
  279.     }
  280.     fillbuf((int) c_len[j]);
  281.     return j;
  282. }
  283.  
  284. local unsigned decode_p()
  285. {
  286.     unsigned j, mask;
  287.  
  288.     j = pt_table[bitbuf >> (BITBUFSIZ - 8)];
  289.     if (j >= NP) {
  290.     mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
  291.     do {
  292.         if (bitbuf & mask) j = right[j];
  293.         else               j = left [j];
  294.         mask >>= 1;
  295.     } while (j >= NP);
  296.     }
  297.     fillbuf((int) pt_len[j]);
  298.     if (j != 0) j = ((unsigned) 1 << (j - 1)) + getbits((int) (j - 1));
  299.     return j;
  300. }
  301.  
  302. local void huf_decode_start()
  303. {
  304.     init_getbits();  blocksize = 0;
  305. }
  306.  
  307. /***********************************************************
  308.         decode.c
  309. ***********************************************************/
  310.  
  311. local int j;    /* remaining bytes to copy */
  312. local int done; /* set at end of input */
  313.  
  314. local void decode_start()
  315. {
  316.     huf_decode_start();
  317.     j = 0;
  318.     done = 0;
  319. }
  320.  
  321. /* Decode the input and return the number of decoded bytes put in buffer
  322.  */
  323. local unsigned decode(count, buffer)
  324.     unsigned count;
  325.     uch buffer[];
  326.     /* The calling function must keep the number of
  327.        bytes to be processed.  This function decodes
  328.        either 'count' bytes or 'DICSIZ' bytes, whichever
  329.        is smaller, into the array 'buffer[]' of size
  330.        'DICSIZ' or more.
  331.        Call decode_start() once for each new file
  332.        before calling this function.
  333.      */
  334. {
  335.     local unsigned i;
  336.     unsigned r, c;
  337.  
  338.     r = 0;
  339.     while (--j >= 0) {
  340.     buffer[r] = buffer[i];
  341.     i = (i + 1) & (DICSIZ - 1);
  342.     if (++r == count) return r;
  343.     }
  344.     for ( ; ; ) {
  345.     c = decode_c();
  346.     if (c == NC) {
  347.         done = 1;
  348.         return r;
  349.     }
  350.     if (c <= UCHAR_MAX) {
  351.         buffer[r] = c;
  352.         if (++r == count) return r;
  353.     } else {
  354.         j = c - (UCHAR_MAX + 1 - THRESHOLD);
  355.         i = (r - decode_p() - 1) & (DICSIZ - 1);
  356.         while (--j >= 0) {
  357.         buffer[r] = buffer[i];
  358.         i = (i + 1) & (DICSIZ - 1);
  359.         if (++r == count) return r;
  360.         }
  361.     }
  362.     }
  363. }
  364.  
  365.  
  366. /* ===========================================================================
  367.  * Unlzh in to out. Return OK or ERROR.
  368.  */
  369. int unlzh(in, out)
  370.     int in;
  371.     int out;
  372. {
  373.     unsigned n;
  374.     ifd = in;
  375.     ofd = out;
  376.  
  377.     decode_start();
  378.     while (!done) {
  379.     n = decode((unsigned) DICSIZ, window);
  380.     if (!test && n > 0) {
  381.         write_buf(out, (char*)window, n);
  382.     }
  383.     }
  384.     return OK;
  385. }
  386.